/**
Quadtree represets a quadtree. Upon initialization, it creates a vector
of rectangles that make up that quadtree. 
 */

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdio.h>
#include <cilk/cilk.h>

#include "Quadtree.h"
#include "IntersectionDetection.h"

inline static bool doesIntersect(Rect* rect, Line* line);
inline static bool isInside(Rect* rect, Line* line);
inline static void splitLines(Rect * rect, vector<Line*>& lines);


//Constructor
Quadtree::Quadtree(vector<Line*>& lines, unsigned int n)
{
  //Set max elements per node.
  maxElements = n;

  //Create the root node
  Rect * root = new Rect;

  //Set the root node.
  getInitRect(lines, root);

  //Divide the root node appropriately until
  //the quadtree has no node with more than 
  //max elements lines. 
  divideRect(root, 1);

  //Set rects.
  list<Rect*> rect_list = cilk_rects.get_value();
  rects.insert(rects.begin(),rect_list.begin(),rect_list.end());
}

//Destructor
Quadtree::~Quadtree()
{
  //Delete all the rectangles of the quadtree.
  for (int i = 0; i < rects.size(); ++i){
    delete rects[i];
  }
}

void Quadtree::getInitRect(vector<Line*>& lines, Rect * rect)
{
  vector<Line*>::iterator it;
 
  double xMin = BOX_XMAX;
  double xMax = BOX_XMIN;
  double yMin = BOX_YMAX;
  double yMax = BOX_YMIN;

  //set the rectangle liens to the given
  //lines. 
  rect->lines = lines;

  //Go through the lines, find the bounds, and create a 
  //rectangle the bounds all the lines.
  for (it = lines.begin(); it != lines.end(); ++it) {
    Line * line = *it;
    if (line->p1.x  < xMin){
      xMin = line->p1.x; 
    }
    if (line->p2.x < xMin){
      xMin = line->p2.x;
    }
    if (line->p1.x > xMax) {
      xMax = line->p1.x;
    }
    if (line->p2.x > xMax) {
      xMax = line->p2.x;
    }
    if (line->p1.y  < yMin){
      yMin = line->p1.y; 
    }
    if (line->p2.y < yMin){
      yMin = line->p2.y;
    }
    if (line->p1.y > yMax) {
      yMax = line->p1.y;
    }
    if (line->p2.y > yMax) {
      yMax = line->p2.y;
    }
  }

  //Using the max and min coordinates of
  //the lines, set the rectangle.
  rect->sw.x = xMin;
  rect->sw.y = yMin;
  rect->nw.x = xMin;
  rect->nw.y = yMax;
  rect->ne.x = xMax;
  rect->ne.y = yMax;
  rect->se.x = xMax;
  rect->se.y = yMin;
}

void Quadtree::divideRect(Rect* parent, int depth)
{
  //If we have less than the max elements or are at max depth,
  //this rectangle does not need to be divided any more.
  if ((parent->lines.size() <= maxElements)||(depth == 20)){
    cilk_rects.push_back(parent);
  }
  else{

    //Divide the rectangle into four quadrants 

    Rect * rect1 = new Rect;
    Rect * rect2 = new Rect;
    Rect * rect3 = new Rect;
    Rect * rect4 = new Rect;

    //Relevant midpoints.
    double wMidX;
    double wMidY;
    double nMidX;
    double nMidY;
    double eMidX;
    double sMidY;

    //Calculate necessary midpoints.
    wMidX = parent->nw.x;
    wMidY = (parent->nw.y+parent->sw.y)/2;
    nMidX = (parent->nw.x+parent->ne.x)/2;
    nMidY = parent->nw.y;
    eMidX = parent->ne.x;
    sMidY = parent->sw.y;

    //Rectangle in bottom left quadrant
    rect1->sw.x = parent->sw.x;
    rect1->sw.y = parent->sw.y;
    rect1->nw.x = wMidX;
    rect1->nw.y = wMidY;
    rect1->ne.x = nMidX;
    rect1->ne.y = wMidY;
    rect1->se.x = nMidX;
    rect1->se.y = sMidY;

    //Rectange in bottom right quadrant
    rect2->sw.x = nMidX;
    rect2->sw.y = sMidY;
    rect2->nw.x = nMidX;
    rect2->nw.y = wMidY;
    rect2->ne.x = eMidX;
    rect2->ne.y = wMidY;
    rect2->se.x = parent->se.x;
    rect2->se.y = parent->se.y;

    //Rectange in top left quadrant
    rect3->sw.x = wMidX;
    rect3->sw.y = wMidY;
    rect3->nw.x = parent->nw.x;
    rect3->nw.y = parent->nw.y;
    rect3->ne.x = nMidX;
    rect3->ne.y = nMidY;
    rect3->se.x = nMidX;
    rect3->se.y = wMidY;

    //Rectange in top right quadrant
    rect4->sw.x = nMidX;
    rect4->sw.y = wMidY;
    rect4->nw.x = nMidX;
    rect4->nw.y = nMidY;
    rect4->ne.x = parent->ne.x;
    rect4->ne.y = parent->ne.y;
    rect4->se.x = eMidX;
    rect4->se.y = wMidY;

    //Put the lines into the appropriate rectangle.
    cilk_spawn splitLines(rect1, parent->lines);
    cilk_spawn splitLines(rect2, parent->lines);
    cilk_spawn splitLines(rect3, parent->lines);
    splitLines(rect4, parent->lines);
    cilk_sync;

    //Delete the parent rectangle (no longer used).
    delete parent;
    
    //Divide the four new rectangles further. 
    cilk_spawn divideRect(rect1, depth+1);
    cilk_spawn divideRect(rect2, depth+1);
    cilk_spawn divideRect(rect3, depth+1);
    divideRect(rect4, depth+1);
    cilk_sync;
  }
}

//Checks if the line intersects the boundary of the
//rectangle.
inline static bool doesIntersect(Rect* rect, Line* line)
{
  return (intersectLines(line->p1, line->p2, rect->sw, rect->nw)||
	  intersectLines(line->p1, line->p2, rect->nw, rect->ne)||
	  intersectLines(line->p1, line->p2, rect->ne, rect->se)||
	  intersectLines(line->p1, line->p2, rect->se, rect->sw));
}

//Checks if the line is inside the rectangle.
inline static bool isInside(Rect* rect, Line* line)
{
  return (pointInParallelogram(line->p1, rect->sw, rect->se, rect->nw, rect->ne)||
	  pointInParallelogram(line->p2, rect->sw, rect->se, rect->nw, rect->ne));
}

//Add all the lines that intersect the given rectangle 
//to the rectangle.
inline void splitLines(Rect * rect, vector<Line*>& lines)
{
  vector<Line*>::iterator it;
  for (it = lines.begin(); it != lines.end(); ++it) {
    if (isInside(rect, *it) || doesIntersect(rect, *it)){
      rect->lines.push_back(*it);
    }
  }
}

vector<Rect*>& Quadtree::getRects()
{
  return rects;
}
